#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;
//#include<string>
//using namespace std;
//class Solution {
//public:
//    bool isPalindrome(string s) {
//        string str;
//        for (auto ch : s)
//        {
//            if (isalnum(ch))
//                str += tolower(ch);
//        }
//        reverse(str.begin(), str.end());
//        return s == str;
//    }
//};
//int main()
//{
//    Solution s;
//   cout<< s.isPalindrome("A man, a plan, a canal: Panama");
//    return 0;
//}
//class Solution {
//public:
//    bool isPalindrome(string s) {
//        string str1, str2;
//        for (auto ch : s)
//        {
//            if (isalnum(ch))
//                str1 += tolower(ch);
//        }
//        str2 = str1;
//        reverse(str1.begin(), str1.end());
//        return str2 == str1;
//    }
//};
//class Solution {
//public:
//    int firstUniqChar(string s) {
//        size_t n = s.size();
//        int count[26] = { 0 };
//        for (auto ch : s)
//        {
//            count[ch - 'a']++;
//        }
//        for (size_t i = 0; i < n; i++)
//        {
//            if (count[s[i] - 'a'] == 1)
//                return i;
//        }
//        return -1;
//    }
//};

//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        int n = nums.size();
//        int left = 0, right = n - 1;
//        while (left < right)
//        {
//            int sum = nums[left] + nums[right];
//            if (sum > target)
//                right--;
//            else if (sum < target)
//                left++;
//            else
//                return vector<int>{left,right };
//        }
//        return vector<int>{ -1,-1};
//    }
//};
//
//int main()
//{
//    vector<int> nums = { 2,7,11,15 };
//    Solution c1;
//    vector<int> ret = c1.twoSum(nums, 9);
//    return 0;
//}

//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        vector<int> sorted_nums = nums;
//        sort(sorted_nums.begin(), sorted_nums.end());
//        int left = 0, right = sorted_nums.size() - 1;
//        while (left < right)
//        {
//            int sum = sorted_nums[left] + sorted_nums[right];
//            if (sum > target)right--;
//            else if (sum < target)left++;
//            else
//                break;
//        }
//        vector<int> ret;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            if (nums[i] == sorted_nums[left] || nums[i] == sorted_nums[right])
//            {
//                ret.push_back(i);
//            }
//            if (ret.size() == 2)
//            {
//                break;
//            }
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums) {
//        vector<vector<int>> ret;
//        sort(nums.begin(), nums.end());
//        int n = nums.size();
//        for (int i = 0; i < n;) {
//            if (nums[i] > 0) break;
//            int left = i + 1, right = n - 1, target = -nums[i];
//            while (left < right) {
//                int sum = nums[left] + nums[right];
//                if (sum > target) --right;
//                else if (sum < target) ++left;
//                else {
//                    ret.push_back({ nums[i],nums[left],nums[right] });
//                    left++, right--;
//                    while (left < right && nums[left] == nums[left - 1]) ++left;
//                    while (left < right && nums[right] == nums[right + 1]) --right;
//                }
//            }
//            ++i;
//            while (i < n && nums[i] == nums[i - 1]) i++;
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target) {
//        sort(nums.begin(), nums.end());
//        vector<vector<int>> ret;
//        int n = nums.size();
//        for (int i = 0; i < n;)
//        {
//            // if(nums[i]>0) break;
//            for (int j = i + 1; j < n;)
//            {
//                int left = j + 1, right = n - 1;
//                long long a = nums[i], b = nums[j];
//                while (left < right)
//                {
//                    long long sum = nums[left] + nums[right];
//                    if (sum > target - a - b)
//                    {
//                        --right;
//                    }
//                    else if (sum < target - a - b)
//                    {
//                        ++left;
//                    }
//                    else
//                    {
//                        ret.push_back({ nums[i],nums[j],nums[left],nums[right] });
//                        ++left;
//                        --right;
//                        while (left < right && nums[left] == nums[left - 1]) ++left;
//                        while (left < right && nums[right] == nums[right + 1])--right;
//                    }
//                }
//                j++;
//                while (j < n && nums[j] == nums[j - 1])j++;
//            }
//            i++;
//            while (i < n && nums[i] == nums[i - 1])i++;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int n = nums.size(), sum = 0, len = INT_MAX;
//        for (int left = 0, right = 0; right < n; right++)
//        {
//            sum += nums[right];
//            while (sum >= target)
//            {
//                len = min(len, right - left + 1);
//                sum -= nums[left++];
//            }
//        }
//        return len == INT_MAX ? 0 : len;
//    }
//};

//class A {
//public:
//	void test(float a)
//	{
//		cout << a;
//	}
//};
//class B : public A {
//public:
//	void test(int b) {
//		cout << b;
//	}
//};
//int main()
//{
//	A* a = new A;
//	B* b = new B;
//	a->test(1.1);
//}
//int main()
//{
//	string arr[] = { "abc" };
//	unordered_map<char, int> a;
//	for (char str : arr)
//		a[str]++;
//	return 0;
//}